1. Field of the Invention
The present invention relates to a method of a cell-layout in an integrated circuit device, and more particularly, relates to a method of a cell-layout according to a Min-Cut layout method.
2. Description of the Prior Art
In a layout method, so-called a Min-Cut layout method, the following processes are repeated hierarchically to position cell-layouts: among a plurality of segments, called cut lines, established on a chip, one segment is selected, and a region on a chip is divided into two by the selected segment, and then cells are assigned (1) to reduce the number of nets (number of cuts) intersected with the cut lines as can be done, and (2) to equalize cell densities in two small regions generated by a division of the region on the chip into two by the cut line. The cell density here defines a ratio of the sum of cell areas assigned in a cell-layout region to cell areas allocable therein.
FIG. 11 is a flow chart showing a method of a cell-layout in an integrated circuit device according to a conventional Min-Cut method. In the drawing, ST1 designates a step of establishing a plurality of segments (hereinafter, referred to as xe2x80x9ccut linesxe2x80x9d) which divides an integrated circuit substrate (hereinafter, referred to as xe2x80x9csubstratexe2x80x9d) in vertical and horizontal directions, ST2 designates a step of assigning all the unplaced cells in the circuit in an entire substrate to be assumed as one cell-layout region, ST4 designates a step of determining a cut-line direction to be next processed in accordance with a predetermined turn, ST5 designates a step of distinguishing a division direction in accordance with the direction determined in the step ST4 to branch the process, ST6 and ST7 designate steps of selecting one cut line per row line and one cut line per column line in the cell-layout region on the substrate among non-processed cut lines in the horizontal and vertical directions, respectively, depending on the direction determined in the step ST4, ST33 denotes a step for processing a Min-Cut division on a single CPU with respect to the cut line selected in the step ST6 or ST7 one by one, ST9 designates a step of marking xe2x80x9cprocessedxe2x80x9d for the cut line selected in the step ST6 or ST7 and renewing cell-layout region information, and ST19 designates a step of distinguishing whether or not the processes have been completed with respect to all the cut lines. The steps ST4, ST5, ST6 or ST7, ST33, ST9, ST19 will be repeated in this order until a distinction that the processes have been completed with respect to all the cut lines in the step ST19.
The Min-Cut division is defined that after a cell-layout region intersected with a cut line is divided into two cell-layout regions by the cut line, the cells assigned at the cell-layout region before the division is transferred to the cell-layout region after the division so as to minimize the number of signal lines intersected with the cut lines and to equalize cell densities in the cell-layout regions after the division.
Next, FIGS. 3, 4, 12-14 are views for an operational explanation related to a conventional method of a cell-layout in an integrated circuit device. In the drawings, reference numerals 21a-21g denote peripheral input/output cells, 22a-22l denote cells to be placed, 23a-23u denote signal lines, 24a-24d denote logic hierarchy blocks, 25 denotes a substrate, 26a-26p denote slots for placing the peripheral input/output cells, 27a-27p denote slots for placing the cells, 28 denotes a wire grid designating a position where wires are passable, 29a-29f denote cut lines for the Min-Cut division process, 31a-31f denote cell-layout regions generated by the division, and 32a-32s denote wiring patterns.
Any one of the peripheral input/output cells 21a-21g may be placed on the slots 26a-26p. The layouts of the peripheral input/output cells are already determined herein, and the peripheral input/output cells 21a-21g are allocated at the slots 26a, 26c, 26f, 26g, 26n, 26k, 26i, respectively. Anyone of the cells 22a-22l may be placed at the inner slots 27a-27p. During a wiring process after the cell-layouts, the wiring patterns may be only passable for parts which are not blocked by the cells or other wires on the wire grids 28.
Referring to the flow chart in FIG. 11, the operation will be next described when the integrated circuit shown in FIG. 3 is placed on the substrate shown in FIG. 4.
In the step ST1 of FIG. 11, the cut lines 29a-29f for dividing the substrate 25 are established. It is here designed that in order to determine the cell-layouts after the divisions have been completed by all the cut lines, only one of the slots is contained in a field enclosed by the cut lines. It is assumed that alternate processes of horizontal and vertical divisions are predetermined with respect to the cut lines 29a-29f. All the cells 22a-22l are assigned as the entire substrate is considered as one cell-layout region in the step ST2. Since an implementation of the horizontal division is determined in the step ST4, the process flow branches to the step ST6 in the step ST5. The cut line 29e which divides the cell-layout region on the substrate is selected in the step ST6. The Min-Cut division is implemented by the cut line 29e in the step ST33.
The cells are here assigned in order to minimize the number of the signal lines intersected with the cut line 29e and to equalize cell densities in the two regions produced by the division. In this manner, as shown in FIG. 12, the two cell-layout regions 31a, 31b are created: in one of these regions, six cells of the cells 22a-22f are assigned on the upper side of the cut line 29e, i.e., on the side of the cell-layout region 31a, while in the other thereof, the remaining cells 22g-22l are assigned on the lower side of the cut line 29e, i.e., on the side of the cell-layout region 31b. In this situation, the signal lines 23g, 23i, 23m intersect with the cut line, and the number of the cuts becomes three. After a determination of the cell assignment, the mark xe2x80x9cdivision-processedxe2x80x9d is prepared for the cut line 29e in the step ST9, and the cell-layout region information is renewed in accordance with the above division-results.
At this point of time, the division by the cut line 29e is completed, the cell-layout region 31a assigned by the cells 22a-22f, and the cell-layout region 31b assigned by the cells 22g-22l are present on the substrate 25. In the next step ST19, the process flow goes back to the step ST4 due to the remaining non-processed cut lines. In the step ST4, an implementation of the vertical division is determined. Thus in the step ST7, the cut line 29b is selected, which divides the cell-layout regions 31a, 31b on the substrate 25 vertically.
Then, the steps ST33, ST9 are implemented with respect to the cut line 29b as well as the cut line 29e, and the division with respect to the cut line 29b is completed. As a result, as shown in FIG. 13, the cell-layout region 31c including the cells 22a, 22b, 22d, the cell-layout region 31d including the cells 22g, 22i, 22j, the cell-layout region 3le including the cells 22c, 22e, 22f, and the cell-layout region 31f including the cells 22h, 22k, 22l come to exist on the substrate 25.
Thereafter, the same divisions as the aforementioned cut lines 29e, 29b are implemented with respect to the cut lines 29d, 29f and the cut lines 29a, 29c in FIG. 4, respectively, until completion of the processes with respect to all the cut lines is distinguished in the step ST19. In these process steps, in the step ST6 the cut lines 29d, 29f are selected, and in the step ST7 the cut lines 29a, 29c are selected, while in the step ST33 the division processes are in turn implemented on a simple CPU one by one with respect to the respective cut lines when a plurality of cut lines are selected in the steps ST6, ST7 as described above.
At the point of time that the divisions with respect to all the cut lines are completed, as shown in FIG. 14, the following cell-layout results are provided: the cells 22a-22l are placed at the slots 27a, 27b, 27d, 27e, 27g, 27i, 27l, 27m, 27n, 27o, 27p, respectively. After the completion of such cell-layouts, one example is illustrated by the wiring patterns 32a-32s in FIG. 14, as a result that the wiring process is implemented between these cells to interconnect the signal lines 32a-32u mutually. As is apparent from FIG. 14, the signal lines 32t, 32u cannot be interconnected, falling in xe2x80x9cwiring incapabilityxe2x80x9d.
Since a method of a cell-layout in an integrated circuit device has the above structure in the prior art as described above, there is a problem that it takes a very long process-time in a large scale integrated circuit since the Min-Cut division is implemented in cell unit and in a single CPU one by one. In addition, there is another problem that in the prior art method there occurs local wire congestion from concentration of signal lines to a part of the regions produced by the division, thus leading easily to signal lines of wiring incapability.
The present invention has been made to solve the above-described problem, and it is an object of the present invention to obtain a method of a cell-layout in an integrated circuit which produces more favorable results of layout and wiring with less local wire congestion in a short process-time.
A method of a cell-layout in an integrated circuit device according to the present invention comprises: a first step of establishing a plurality of cut lines in vertical and horizontal directions to divide a substrate; a second step of considering the entire substrate as one cell-layout region and assigning all the cells included in an integrated circuit in said cell-layout region; a third step of defining as one cluster a set of a plurality of cells within said cell-layout region; a fourth step of determining a direction of the cut line to division-process said cell-layout region; a fifth step of selecting one cut line per row or column of the cell-layout region on the substrate among non-processed cut lines in the horizontal or vertical direction based on the determined direction; a sixth step of determining a cell in said cell-layout region by implementing a Min-Cut division in cluster unit with respect to the selected cut line, thereby dividing the substrate into small regions, and implementing said division in parallel with respect to a plurality of the cut lines.
Thus, when there are a plurality of the cut lines in the same direction, the above division-processes may be implemented independently of each other; therefore, an implementation of parallel processes on a multiple CPUs results in reducing a process time while keeping a quality of the cell-layout.
The method according to the present invention further comprises: a seventh step for comparing the number of the cell-layout regions with a predetermined value; an eighth step for changing a height of said cell-layout region so as to equalize an estimated value of virtual wire congestion degree in a horizontal wire within the cell-layout region on the same column, and implementing again the cell-layout within the cell-layout region changed in height; and a ninth step for changing a width of said cell-layout region so as to equalize an estimated value of virtual wire congestion degree in a vertical wire within the cell-layout region on the same row, and implementing again the cell-layout within the cell-layout region changed in width.
Thus, even when the signal lines concentrate on a part of the cell-layout regions produced by divisions for the purpose of minimizing the number of the cuttings, the width or height of the cell-layout region is changed to equalize the virtual wire congestion degree, and then the division of the cell-layout region intersecting with the processed cut line by that change is implemented again; such a process of equalizing the virtual wire congestion degree in each of the regions is implemented, resulting in cell-layouts with less local wire congestion.
The method according to the present invention is characterized in that in the third step, by use of logic hierarchy structure information added to the cells at the time of a logic design of the integrated circuit, defined as a cluster is a set of cells included in the largest logic hierarchy block among those smaller than an upper limit of a cluster size determined in response to the size of the small region generated by the division of the cell-layout region by the cut line.
Thus, with the progress of that division, a set of cells included in the lower logic hierarchy block with the progress of the division is defined as a cluster, which results in cutting further the process-time.
The method according to the present invention is characterized in that in the third step, defined as a cluster is only a block such that a ratio of the number of signal lines connected with only the cells within the logic hierarchy block to the number of signal lines connected with said cells is larger than a predetermined reference value, which results in a favorable cell-layout result.
The method of the present invention is characterized in that the Min-Cut division with respect to the plurality of cut lines in the sixth step is implemented in independent, parallel process by a plurality of CPUs.
Thus, even when a large scale integrated circuit is processed, the division by a plurality of cut lines may be implemented with concurrent proceeding of the plurality of CPUs, resulting in implementing the cell-layout in a short process time.